// 53. 最大子数组和
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    const len = nums.length
    if (len === 1) return nums[0]
    const memo = Array(len).fill(0)
    memo[0] = nums[0]
    let max = nums[0]
    for (let i = 1; i < len; i++) {
        memo[i] = Math.max(memo[i - 1] + nums[i], nums[i])
        if (memo[i] > max) {
            max = memo[i]
        }
    }

    return max
};
// 压缩状态
var maxSubArray = function (nums) {
    let prev = 0, maxAns = nums[0]
    nums.forEach(num => {
        prev = Math.max(prev + num, num)
        maxAns = Math.max(prev, maxAns)
    });
    return maxAns
}
maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])